package com.gitee.feizns.explore.data_structure.union_find;

/**
 * 130. 被围绕的区域
 * @author feizns
 * @since 2020/3/11
 */
public class Solve {

//[
// ["O","X","X","O","X"],
// ["X","O","O","X","O"],
// ["X","O","X","O","X"],
// ["O","X","O","O","O"],
// ["X","X","O","X","O"]
// ]

    public static void main(String[] args) {
        char[][] board = new char[][]{
            {'O', 'X', 'X', 'O', 'X'},
            {'X', 'O', 'O', 'X', 'O'},
            {'X', 'O', 'X', 'O', 'X'},
            {'O', 'X', 'O', 'O', 'O'},
            {'X', 'X', 'O', 'X', 'O'}
        };
        new Solve().solve(board);
    }

// 并查集

    public void solve(char[][] board) {
        if ( board == null || board.length < 2 || board[0].length < 2 )
            return;
        int r = board.length;
        int c = board[0].length;
        int size = r * c;
        int dummy = size;
        Uf uf = new Uf(size + 1);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if ( board[i][j] == 'O' ) {
                    int index = i * c + j;
                    if ( i == 0 || j == 0 || i == board.length - 1 || j == board[0].length - 1 )
                        uf.union(index, dummy);
                    else {
                        int tmp;
                        if ( (tmp = index(i + 1, j, board)) != -1 && board[i + 1][j] == 'O' )
                            uf.union(index, tmp);
                        if ( (tmp = index(i - 1, j, board)) != -1 && board[i - 1][j] == 'O' )
                            uf.union(index, tmp);
                        if ( (tmp = index(i, j + 1, board)) != -1 && board[i][j + 1] == 'O' )
                            uf.union(index, tmp);
                        if ( (tmp = index(i, j - 1, board)) != -1 && board[i][j - 1] == 'O' )
                            uf.union(index, tmp);
                    }
                }
            }
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                int index = index(i, j, board);
                if ( !uf.isConnected(index, dummy) )
                    board[i][j] = 'X';
            }
        }
    }

    private int index(int x, int y, char[][] board) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length ? x * board[0].length + y : -1;
    }

    static class Uf {
        int[] parents;
        int[] rank;
        public Uf(int size) {
            parents = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++)
                parents[i] = i;
        }
        public boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }
        public void union(int p, int q) {
            int qr = find(p);
            int pr = find(q);
            if ( qr != pr ) {
                if ( rank[qr] < rank[pr] )
                    parents[qr] = pr;
                else if ( rank[qr] > rank[pr] )
                    parents[pr] = qr;
                else {
                    parents[qr] = pr;
                    rank[pr]++;
                }
            }
        }
        public int find(int q) {
            while ( q != parents[q] ) {
                parents[q] = parents[parents[q]];
                q = parents[q];
            }
            return q;
        }
    }





// 常规：dfs

//[
// ["X","O","X","O","X","O"],
// ["O","X","O","X","O","X"],
// ["X","O","X","O","X","O"],
// ["O","X","O","X","O","X"]
// ]
//
//    char[][] board;
//
//    int[] marks;
//
//    public void solve(char[][] board) {
//        if ( board == null || board.length < 2 || board[0].length < 2 )
//            return;
//        this.board = board;
//        this.marks = new int[board.length * board[0].length];
//        for (int i = 0; i < board[0].length; i++)       //上
//            dfs(0, i);
//        for (int i = 1; i < board.length; i++)          //右
//            dfs(i, board[0].length - 1);
//        for (int i = 1; i < board[0].length - 1; i++)   //下
//            dfs(board.length - 1, i);
//        for (int i = 1; i < board.length; i++)          //左
//            dfs(i, 0);
//
//        for (int i = 0; i < board.length; i++) {
//            for (int j = 0; j < board[0].length; j++) {
//                int index = i * board[0].length + j;
//                if ( marks[index] == 0 && board[i][j] == 'O' )
//                    board[i][j] = 'X';
//            }
//        }
//    }
//
//    private void dfs(int x, int y) {
//        int index = x * board[0].length + y;
//        if ( in(x, y) && marks[index] == 0 && board[x][y] == 'O' ) {
//            marks[index] = 1;
//            dfs(x - 1, y);
//            dfs(x + 1, y);
//            dfs(x, y - 1);
//            dfs(x, y + 1);
//        }
//    }
//
//    private boolean in(int x, int y) {
//        return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
//    }

}
